package com.peng.leetcode.tree;

/**
 * IsBalanced1
 * 110. 平衡二叉树
 * https://leetcode.cn/problems/balanced-binary-tree/
 * 1. 使用自顶向下计算，每个节点取左右子树最大高度计算啊高度差 > 1 返回false，时间复杂度 o(n * n)
 * 2. 自底向上计算，时间复杂度 o(n)
 * <p>
 * Created on 2022/11/30
 *
 * @author lupeng
 */
public class IsBalanced1 {
    public boolean isBalanced(TreeNode root) {
        return dfs(root) > -1;
    }

    int dfs(TreeNode n) {
        if (n == null) {
            return 0;
        }
        int leftDepth = dfs(n.left);
        int rightDepth = dfs(n.right);
        if (leftDepth == -1 || rightDepth == -1 || Math.abs(leftDepth - rightDepth) > 1) {
            return -1;
        }
        return Math.max(leftDepth, rightDepth) + 1;
    }
}
